package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

/**
 * @author feizns
 * @since 2019/12/9
 */
public class IsSymmetric {

    public static void main(String[] args) {
        System.out.println(isSymmetric(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.right = new TreeNode(2);
        ret.left.right = new TreeNode(4);
        ret.right.right = new TreeNode(4);
        return ret;
    }

//    public static boolean isSymmetric(TreeNode root) {
//        return isSymmetric(Arrays.asList(root));
//    }

    public static boolean isSymmetric(TreeNode root) {
        if ( root != null ) {
            Queue<TreeNode> queue1 = new LinkedList<>();
            Queue<TreeNode> queue2 = new LinkedList<>();
            queue1.add(root);
            queue2.add(root);
            while ( !queue1.isEmpty() && !queue2.isEmpty() ) {
                TreeNode q1 = queue1.remove();
                TreeNode q2 = queue2.remove();

                if ( q1 != null && q2 != null && q1.val != q2.val )
                    return false;
                else if ( (q1 != null && q2 == null) || (q1 == null && q2 != null) )
                    return false;

                if ( q1 != null ) {
                    queue1.add(q1.left);
                    queue1.add(q1.right);
                }

                if ( q2 != null ) {
                    queue2.add(q2.right);
                    queue2.add(q2.left);
                }
            }

            return queue1.isEmpty() && queue2.isEmpty();
        }

        return true;
    }

    private static boolean isSymmetric(List<TreeNode> list) {
        if ( list.stream().allMatch(Objects::isNull) )
            return true;

        for (int i = 0; i < list.size() >> 1; i++) {
            TreeNode left = list.get(i);
            TreeNode right = list.get(list.size() - 1 - i);
            if ( left != null && right != null && left.val != right.val )
                return false;
            if ( left == null && right != null )
                return false;
            if ( right == null && left != null )
                return false;
        }

        List<TreeNode> nextLevel = new LinkedList<>();
        for (TreeNode treeNode : list) {
            if ( treeNode != null ) {
                nextLevel.add(treeNode.left);
                nextLevel.add(treeNode.right);
            }
        }

        return isSymmetric(nextLevel);
    }


}
